package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/9/20.
 * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
 * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 */
public class TreeNextNode {
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }

    /**
     * 中序遍历是直先遍历节点的左子树，然后是节点本身，然后是节点的右子树。
     * 前序遍历是先是节点本身，然后左子树，再之后是右子树。
     * 后序遍历是先左子树,后右子树，最后是节点本身
     * 在子树中的遍历规则同上
     * */
    public TreeLinkNode GetNext(TreeLinkNode pNode){
        if(pNode == null) return null;
        //若右子树不为空，把其右孩子作为下一个遍历的节点
        //然后沿着该节点的左子树出发，直到遇到叶子节点，该叶子节点就是下一个要找的节点
        if (pNode.right != null){
            pNode = pNode.right;
            while (pNode.left != null){
                pNode = pNode.left;
            }
            return pNode;
        }
        //没有右子树，则判断该节点是否是其父节点的左孩子，
        // 如果是则其下一个要找的节点是其父节点；
        // 如果不是其父节点的左孩子，则把其父节点作为下一个遍历的节点，向上回溯
        while (pNode.next != null){
            //由于是中序遍历，所以next即为该节点的父节点
            if (pNode.next.left == pNode){
                return pNode.next;
            }
            pNode = pNode.next;
        }
        return null;
    }
}
